package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/12/10 19:37
 */
public class No55_跳跃游戏 {
    public static void main(String[] args) {
        Solution55 solution55 = new Solution55();
        int[] nums = new int[]{
                2, 3, 4, 3, 3, 0, 1, 0, 7
        };
        boolean b = solution55.canJump(nums);
        System.out.println(b);
    }
}


class Solution55 {
    public boolean canJump(int[] nums) {
        //贪心算法,如果想要了解原理,No45_跳跃游戏II有说明
        
        
        //定义红指针,代表当前位置
        int red = 0;
        //定义根据红指针出现的路径范围
        int green1 = 0;
        int grren2 = 0;
        
        //定义跳跃最远判断
        int jump = 0;
        while (true) {
            //nums {0}
            green1 = red + 1;
            //nums {7,6,0,0,0}
            grren2 = nums[red] + red;

            // nums {0,1}
            if (green1 >= nums.length || grren2 >= nums.length) {
                break;
            }
            
            //绿色部分找跳最远
            for (int i = green1; i <= grren2; i++) {
                if (nums[i] + i >= jump) {
                    red = i;
                    jump = nums[i] + i;
                }
            }
            
            //找出之后,判断能否到终点??
            if (red != nums.length - 1 && nums[red] == 0) {
                //红指针没到终点,且值为0,无法运动
                return false;
            }
            
        }
        return true;
    }
}



    //public boolean canJump(int[] nums) {
    //    //建议先行观看No45_跳跃游戏II 里面的动态规划方法
    //    //再进行,有助于思维的瞬间加固
    //    
    //    //处理nums第一个元素是黑域问题!!
    //    if (nums.length == 1) {
    //        return true;
    //    } else if (nums[0] == 0) {
    //        return false;
    //    }
    //    
    //    //定义动态规划:dp[n]为跳跃n位置的最小次数
    //    //所以,如果无法跳跃,则dp[x] = 无穷
    //    int[] dp = new int[nums.length];
    //    //初始化
    //    dp[0] = 0;
    //    
    //    //nums[0,1]
    //    dp[1] = 1;
    //    
    //    //开始动态规划
    //    for (int n = 2; n <= nums.length - 1; n++) {
    //        //dp[4]为栗:n=4,从0开始算
    //        for (int j = 0; j <= n - 1; j++) {
    //            //如何判断j位置能到n位置??
    //            if (nums[j] + j >= n) {
    //                dp[n] = dp[j] + 1;
    //                break;
    //            }
    //            
    //            //还有个问题:判断无法跳跃??
    //            if (j == n - 1 && nums[j] + j < n) {
    //                return false;
    //            }
    //        }
    //    }
    //    return true;
    //}






